package 单链表;

/**
 * @Description 单链表
 * 链表是有序的列表
 * ①链表是以节点的方式来存储,是链式存储
 * ②每个节点包含 data 域， next 域：指向下一个节点.
 * ③发现链表的各个节点不一定是连续存储.
 * ④链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
 * <p>
 * 添加（创建）
 * 1. 先创建一个head 头节点， 作用就是表示单链表的头
 * 2. 后面我们每添加一个节点，就直接加入到  链表的最后
 * 遍历：
 * 1.  通过一个辅助变量遍历，帮助遍历整个链表
 * @Author 俊昭
 * @Date 2022/4/27
 * @version 1.1 2022/4/28 修复了不可以删除第一个节点的bug
 *  对set、del进行了优化
 */
public class SingleLinkedList {
    // 管理Node
    // 初始化一个头节点 且不可以改动！不存放具体数据
    private final Node head = new Node(0, "", "");
    /*
       增
    // 不考虑编号顺序时，直接添加到链表的尾部
    // ①找到当前链表的最后一个节点
    // ②将最后一个节点 nextNode 指向新的 Node
    public void add(Node newNode) {
        Node temp = this.head;
        while (temp.nextNode != null) {
            temp = temp.nextNode;
        }
        temp.nextNode = newNode;
    }
    已废弃
    */

    /**
     * @param newNode 新的好汉对象
     * @description 增
     * 添加时，根据排名插入到指定位置 如果有这个排名，则添加失败，并给出提示
     * @author 俊昭
     * @date 2022/4/27
     */
    public void add(Node newNode) {
        Node temp = this.head;
        int no = newNode.No;
        while (true) {
            if (no == temp.No) {
                System.out.println("好汉已存在,请检查信息:" + " " + newNode);
                break;
            } else if (temp.nextNode == null) {
                temp.nextNode = newNode;
                break;
            } else if (no > temp.No && no < temp.nextNode.No) {
                newNode.nextNode = temp.nextNode;
                temp.nextNode = newNode;
                break;
            }
            temp = temp.nextNode;
        }
    }

    /**
     * @param No 好汉排名
     * @description 删
     * 从链表中移除节点
     * 实现方式 使被删除的节点的前一个节点的nextNode指向下一个节点
     * @author 俊昭
     * @date 2022/4/27
     * @since 1.1
     */
    public void del(int No) {
        if (head.nextNode == null) {
            System.out.println("表中还未有信息");
        } else {
            Node temp = head;
            while (true) {
                if (temp.nextNode.No == No) {
                    temp.nextNode = temp.nextNode.nextNode;
                    break;
                }
                temp = temp.nextNode;
            }
        }
    }

    /**
     * @param newNode 新的好汉对象
     * @description 改
     * 修改一个节点信息 编号不改变只改变信息
     * @author 俊昭
     * @date 2022/4/27
     */
    public void set(Node newNode) {
        if (head.nextNode == null) {
            System.out.println("表中还未有信息");
        } else {
            Node temp = head.nextNode;
            while (temp != null) {
                if (temp.No == newNode.No) {
                    temp.name = newNode.name;
                    temp.desc = newNode.desc;
                    break;
                }
                temp = temp.nextNode;
            }
            if (temp == null) {
                System.out.println("您输入的好汉编号不存在，请检查");
            }
        }

    }

    /**
     * @param No 好汉排名
     * @description 查
     * 输入好汉排名 若有 打印其信息；无 给出提示。
     * @author 俊昭
     * @date 2022/4/27
     */
    public void get(int No) {
        if (head.nextNode == null) {
            System.out.println("表中还未有信息");
        } else {
            Node temp = head.nextNode;
            while (temp != null) {
                if (temp.No == No) {
                    System.out.print("找到排名" + No + "好汉信息");
                    System.out.println(temp);
                    return;
                }
                temp = temp.nextNode;
            }
            System.out.println("未找到好汉信息");
        }
    }

    // 显示链表
    public void show() {
        if (head.nextNode != null) {
            Node temp = this.head;
            while (temp.nextNode != null) {
                temp = temp.nextNode;
                System.out.println(temp);
            }
            System.out.println();
        } else {
            System.out.println("表中还未有信息");
        }
    }

    //单链表面试题常见面试题如下:

    //求单链表中有效节点的个数
    public int effectiveNode() {
        if (head.nextNode != null) {
            int i = 0;
            Node temp = head.nextNode;
            while (temp != null) {
                temp = temp.nextNode;
                i++;
            }
            return i;
        } else {
            return - 1;
        }
    }

    //查找单链表中的倒数第k个结点 【新浪面试题】
    public Node getNokNode(int k) {
        if (k <= effectiveNode()) {
            int times = effectiveNode() - k;
            Node temp = head.nextNode;
            for (int i = 0; i < times; i++) {
                temp = temp.nextNode;
            }
            return temp;
        } else {
            return null;
        }
    }

    //单链表的反转【腾讯面试题，有点难度】

    /**
     * @description 有点意思~~
     * @author 俊昭
     * @date 2022/4/27
     */
    public void reverse() {
        if (head.nextNode != null) {
            Node rNodeHead = new Node(0, "", "");
            Node temp = head.nextNode;// 定义一个辅助指针
            while (temp != null) {// 指针不空就继续
                Node t = temp.nextNode;// 复制一份
                if (rNodeHead.nextNode == null) {// 对另一歌单链表初始化
                    rNodeHead.nextNode = temp;
                    rNodeHead.nextNode.nextNode = null;// 一定将Node尾指针null
                } else {
                    temp.nextNode = rNodeHead.nextNode;// 插入到头部
                    rNodeHead.nextNode = temp;
                }
                temp = t;
            }
            head.nextNode = rNodeHead.nextNode;// 主指针空了 就讲新的链表连接回原单链表
        } else {
            System.out.println("还未有Node");
        }
    }
    //从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】
    // 思路
    //1. 上面的题的要求就是逆序打印单链表.
    //2. 方式1： 先将单链表进行反转操作，然后再遍历即可，这样的做的问题是会破坏原来的单链表的结构，不建议
    //3. 方式2：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果.
    // 举例演示栈的使用 Stack 等到栈的时候再说

    /**
     * @param list 一个要加入的列表
     * @return [单链表.SingleLinkedList]
     * @description 合并两个有序的单链表，合并之后的链表依然有序【课后练习.】
     * @author 俊昭
     * @date 2022/4/27
     */
    public SingleLinkedList merge(SingleLinkedList list) {
        if (this == list) {
            return this;
        }
        // 判空
        if (head.nextNode == null && list.head.nextNode == null) {
            return null;
        } else if (head.nextNode == null) {
            return list;
        } else if (list.head.nextNode == null) {
            return this;
        }
        // 不空就加入
        Node temp = head.nextNode;
        while (temp != null) {
            Node t = temp.nextNode;
            temp.nextNode = null;// 一定记得这一行！！！很重要
            list.add(temp);
            temp = t;
        }
        return list;
    }
}

class test {
    public static void main(String[] args) {
        SingleLinkedList sll = new SingleLinkedList();

        // 打乱顺序的地插入
        sll.add(new Node(1, "宋江", "及时雨"));
        sll.add(new Node(4, "公孙胜", "入云龙"));
        sll.add(new Node(3, "吴用", "智多星"));
        sll.add(new Node(2, "卢俊义", "玉麒麟"));
        sll.add(new Node(6, "林冲", "豹子头"));
        sll.add(new Node(21, "刘唐", "赤发鬼"));
        sll.add(new Node(14, "武松", "行者"));
//        // 输入错误信息使用set()修改 这条信息是错误的
//        sll.add(new Node(13, "林冲", "豹子头"));
//        sll.show();
//
//        // 输入重复no的信息
//        sll.add(new Node(3, "AA", "AA"));
//
//        sll.set(new Node(13, "鲁智深", "花和尚"));
//        sll.show();
//        // 删除某一信息
//        sll.del(6);
//        sll.show();
//
//        // 查找
//        sll.get(6);
//        sll.get(14);

        sll.show();
        // 有效节点数
        System.out.println(sll.effectiveNode());
        // 倒数第k个节点
        System.out.println(sll.getNokNode(2) + "\n");

        sll.reverse();
        sll.show();

        // 合并两链表
        SingleLinkedList sll2 = new SingleLinkedList();
        sll2.add(new Node(5, "关胜", "大刀"));
        sll2.add(new Node(9, "花荣", "小李广"));
        sll2.add(new Node(8, "呼延灼", "双鞭"));
        sll2.show();

        sll = sll.merge(sll2);
        sll.show();


    }
}

class Node {
    // 定义一个Node元素
    public int No;
    public String name;// 名字
    public String desc;// 描述
    public Node nextNode;// 下一个元素

    public Node(int no, String name, String desc) {
        No = no;
        this.name = name;
        this.desc = desc;
    }

    /**
     * 重写toString
     *
     * @return 返回一位英雄的各信息
     */
    @Override
    public String toString() {
        return "好汉{" +
                "排名 " + No +
                ", 姓名 " + name +
                ", 诨号 " + desc +
                '}';
    }
}